Jolt

(updated )

$$ \gdef\mat#1{\mathrm{#1}} \gdef\p#1{\left({#1}\right)} \gdef\ceil#1{\left\lceil{#1}\right\rceil} \gdef\forall{\mathop{\huge ∀}\limits} $$

Notes studying Jolt. Per Michael Zhu's suggestion I will follow the lineage from Spice SAGL18, Spartan S19, Lasso STW23, Jolt AST23, Binius DP23.

Spice

Spartan

Spartan (S19) is a transparant zkSNARK for R1CS. Recal an R1CS instance over a field $𝔽$ with $n$-sparse $m×m$ matrices $\mat A, \mat B, \mat C$ such that a $z=(1,\mathsf{pub},\mathsf{priv})$ satisfies iff $(\mat A⋅ z) ∘(\mat B ⋅ z) = \mat C ⋅ z$. We convert this to a sumcheck zero testing statement $$ \forall_{x∈\{0,1\}^s}0= \p{\sum_{y∈\{0,1\}^s}\widetilde A(x,y)⋅\widetilde z(y)}⋅ \p{\sum_{y∈\{0,1\}^s}\widetilde B(x,y)⋅\widetilde z(y)}\\- \sum_{y∈\{0,1\}^s}\widetilde C(x,y)⋅\widetilde z(y) $$ where $\widetilde\square$ denotes a multilinear extension and $s=\ceil{\log_2 m}$.Batching the inner sumchecks, it takes two sumchecks to reduce this to $$ (r_A⋅\widetilde A(r_x, r_y) + r_B⋅\widetilde B(r_x, r_y) + r_C⋅\widetilde C(r_x, r_y)) ⋅ \widetilde z(r_y) $$ For $\widetilde z$ the prover provides a hiding polynomial commitment to $\mathsf{priv}$ up front and reveals it at $r_y$ so that the verifier can compute $\widetilde z(r_y)$. The verifier knows $\widetilde A, \widetilde B, \widetilde C$ and can evaluate it directly.

Evaluating the $\widetilde A, \widetilde B, \widetilde C$ takes $O(n)$ work. To solve this the verifier pre-computes commitments to them and the prover computes openings. To be efficient, this requires a polynomial commitements scheme that is efficient for sparse polynomials. Consider $\widetilde A$ (the other cases are identical) we have the $n$ term sum $$ \widetilde A(r_x, r_y) = \sum_{\begin{subarray}{c} i,j ∈ \{0,1\}^s \\[.3em] \mat A_{ij} ≠ 0 \end{subarray}} \mat A_{ij} ⋅ \widetilde{\operatorname{eq}}(i, r_x)⋅\widetilde{\operatorname{eq}}(j, r_y) $$ where $\widetilde{\operatorname{eq}}$ is the multilinear equality function.

To evaluate this we create lookup tables for $\widetilde{\operatorname{eq}}(i, r_x)$, $\widetilde{\operatorname{eq}}(j, r_y)$ and the sequence of $(i,j, \mat M_{ij})$ tuples to sum over.

Create three vectors, $i$, $j$ and $M_{ij}$.

References

Remco Bloemen
Math & Engineering
https://2π.com